//
// Created by user on 2022/3/15.
//

#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
ListNode* reverseList(ListNode* head) {
    if(!head || !head->next){
        return head;
    }
    ListNode *p = reverseList(head->next);

    head->next->next = head;
    head->next = nullptr;

    return p;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode *dummy = new ListNode(-1);
    dummy->next = head;
    ListNode *prev = dummy;
    for (int i = 0; i < left-1; ++i) {
        prev = prev->next;
    }
    ListNode *leftNode = prev->next;

    ListNode *rightNode = leftNode;

    for (int i = 0; i < right-left; ++i) {
        rightNode = rightNode->next;
    }

    ListNode *postNode = rightNode->next;

    //切断
    prev->next = nullptr;
    rightNode->next = nullptr;

    //反转
    reverseList(leftNode);

    //拼接
    prev->next = rightNode;
    leftNode->next=postNode;

    return dummy->next;
}

//一次遍历
// 头插法
ListNode* reverseBetween1(ListNode* head, int left, int right) {
    ListNode* dummyNode = new ListNode(-1);
    dummyNode->next = head;

    ListNode *prev = dummyNode;
    for (int i = 0; i < left - 1; i++) {
        prev = prev->next;
    }

    ListNode *curr = prev->next;
    for (int i = 0; i < right - left; i++) {
        ListNode *next = curr->next;
        curr->next = next->next;
        next->next = prev->next;
        prev->next = next;
    }

    return dummyNode->next;
}